//
//  归并排序.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/1.
//

import UIKit

class GuiBing: NSObject {
    var array = [Int]()
    var leftArray = [Int]()
    func sort(_ array: [Int]) -> [Int] {
        self.array = array
        fenGe(0, array.count)
        return self.array
    }
    
    func fenGe(_ begin: Int, _ end: Int ) {
        if end - begin < 2 {
            return
        }
        let middle = (begin + end) / 2
        fenGe(begin, middle)
        fenGe(middle, end)
        marge(begin, middle, end)
    }
    
    func marge(_ begin: Int, _ middle: Int ,_ end: Int) {
        var li = 0
        let le = middle - begin
        var ri = middle
        let re = end
        var aIndex = begin
        leftArray.removeAll()
        // 处理左边备份
        for index in li..<le {
            leftArray.append(array[begin + index])
        }
        // 合并移动
        while li < le {
            if ri < re && leftArray[li] > array[ri] {
                array[aIndex] = array[ri]
                ri += 1
            } else {
                array[aIndex] = leftArray[li]
                li += 1
            }
            aIndex += 1
        }
        
    }

    
}
